﻿/*  ----------------------------------------------------------------------------
 *  SysServer
 *  ----------------------------------------------------------------------------
 *  File:       TQueue`1.cs
 *  Creater:     SEEN\MistSeen
 *  ----------------------------------------------------------------------------
 *  $Date: 2010-09-06 10:36:01 +0000 (Mon, 06 Sep 2010) $
 *  $Rev: 15 $
 *  $Author: ScorDeity $
 *  $URL: http://sysserver.googlecode.com/svn/trunk/src/SysServer/Collections/Generic/TQueue%601.cs $
 *  $Id: TQueue`1.cs 15 2010-09-06 10:36:01Z ScorDeity $
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace SysServer.Collections.Generic
{
    //http://www.google.com/codesearch/p?hl=zh-CN#HhXS9_5bsiE/trunk/DataStructures/LockfreeQueue.cs&q=SocketAsyncEventArgs&t=0&d=1

    public class TQueueNode<T> : TEntity
    {
        public T Data;
        public TQueueNode<T> Next;

        public TQueueNode()
        {

        }
        public TQueueNode(T data)
        {
            this.Init(data);
        }
        public override void Initialize()
        {
            this.Init(default(T));
        }
        private void Init(T data)
        {
            this.Data = data;
            this.Next = null;
        }
    }


    /// <summary>
    /// 无锁队列
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class TQueue<T>
    {
        private TQueueNode<T> _Head;
        private TQueueNode<T> _Tail;

        public TQueue()
        {
            this._Head = this._Tail = new TQueueNode<T>();
        }

        public void Enqueue(T data)
        {
            TQueueNode<T> oldTail = null;
            TQueueNode<T> oldTailNext = null;
            TQueueNode<T> newNode = new TQueueNode<T>();

            newNode.Data = data;

            do
            {
                oldTail = this._Tail;
                oldTailNext = this._Tail.Next;

                if (oldTail == this._Tail)
                {
                    if (oldTailNext == null)
                    {
                        if (Interlocked.CompareExchange<TQueueNode<T>>(ref oldTail.Next, newNode, oldTailNext) == oldTailNext)
                        {
                            break;
                        }
                    }
                    else
                    {
                        Interlocked.CompareExchange<TQueueNode<T>>(ref this._Tail, oldTailNext, oldTail);
                    }
                }
            } while (true);

            Interlocked.CompareExchange<TQueueNode<T>>(ref this._Tail, newNode, oldTail);
        }
        /// <summary>
        /// 
        /// </summary>
        /// <param name="date"></param>
        /// <returns></returns>
        public bool Dequeue(out T date)
        {
            date = default(T);
            TQueueNode<T> oldTail = null;
            TQueueNode<T> oldHead = null;
            TQueueNode<T> oldHeadNext = null;

            do
            {
                oldTail = this._Tail;
                oldHead = this._Head;
                oldHeadNext = oldHead.Next;

                if (oldHead == this._Head)
                {
                    if (oldHead != oldTail)
                    {
                        if (oldHead == null)
                        {
                            return false;
                        }
                        Interlocked.CompareExchange<TQueueNode<T>>(ref this._Tail, oldHeadNext, oldTail);
                    }
                    else
                    {
                        if (Interlocked.CompareExchange<TQueueNode<T>>(ref this._Head, oldHeadNext, oldHead) == oldHead)
                        {
                            date = oldHeadNext.Data;
                            break;
                        }

                    }
                }
            } while (true);
            oldHead.Data = default(T);
            //TODO:
            return true;
        }
        public T Dequeue()
        {
            T result;

            Dequeue(out result);

            return result;
        }
    }
}